package easy;

import java.util.HashSet;
import java.util.Set;

public class Solution_189 {

    public static void rotate2(int[] nums, int k) {
        if (nums==null || nums.length<2) {
            return;
        }
        int kk = k%nums.length;
        if (kk==0) {
            return;
        }
        int temp = nums[kk];
        for(int now = kk;;) {
            int pre = (now-kk+nums.length)%nums.length;
            nums[now] = nums[pre];
            now--;
            if (now<0){
                now += nums.length;
            }
            if (now==kk) {
                break;
            }
        }
    }

    public static void rotate(int[] nums, int k) {
        if (nums==null || nums.length<2) {
            return;
        }
        int kk = k%nums.length;
        if (kk==0) {
            return;
        }
        int count = 0;
        Set<Integer> mods = new HashSet<>();
//        int max = max(nums.length, kk);
//        System.out.println("max:"+max);
        for (int mod = kk; mod > 0; mod--) {
            if (mods.contains(mod)) {
                break;
            }
            int index = mod, temp, originValue = nums[index];//原值
            while (true) {
                count++;
                index += kk;
                if (index>=nums.length) {
                    index %= nums.length;
                    mods.add(index);
//                    mods.forEach(m-> System.out.print(m+","));
//                    System.out.println();
                }

                temp = nums[index];//目标值
                nums[index] = originValue;
                if (index==mod) {
                    break;
                }
                originValue = temp;
            }
        }
        System.out.println(count);
    }

    private static int max(int v1, int v2){
        int min = Math.min(v1, v2);
        if (min==1) return 1;
        for (int i = 2; i <= min; i++) {
            if (v1%i==0 && v2%i==0){
                return i;
            }
        }
        return 1;
    }

    public static void main(String[] args) {
//        System.out.println(max(4, 2));
        int[] nums = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54};
        rotate(nums, 45);
        for (int num : nums) {
            System.out.print(num+",");
        }
        System.out.println();
    }
}
